/*
Source : https://leetcode.com/problems/first-missing-positive/
Author : nflush@outlook.com
Date   : 2016-07-18
*/

/*
41. First Missing Positive
 ?  

Question Editorial Solution  
 My Submissions 




?Total Accepted: 69283
?Total Submissions: 286442
?Difficulty: Hard



Given an unsorted integer array, find the first missing positive integer. 

For example,
 Given [1,2,0] return 3,
 and [3,4,-1,1] return 2. 

Your algorithm should run in O(n) time and uses constant space. 



Subscribe to see which companies asked this question
*/
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int size = nums.size();
        for (int i = 0; i < size; i++){
//            if (nums[i] < 0 || nums[i] > size){
//                nums[i] = 0;
//            } else {
                int x = nums[i];
                while (x > 0 && x <= size && nums[x-1] != x){
                    int y = nums[x-1];
                    nums[x-1] = x;
                    x = y;
                }
//            }
            
        }
        for (int i = 0; i <size;i++){
            if (nums[i] != i+1) return i+1;
        }
        return size + 1;
    }
};
